1부터 N까지 숫자 중 합이 10이 되는 조합 구하기

#Algo

📔 문제 설명

정수 N을 입력받아 1부터 N까지의 숫자 중에서 합이 10이 되는 조합을 배열로 반환하는 solution()함수를 작성하세요.

📓 제약 조건

백트래킹을 활용해야 합니다.
숫자 조합은 오름차순으로 정렬되어야 합니다.
같은 숫자는 한 번만 선택할 수 있습니다.
N은 1 이상 10 이하인 정수입니다.

📓 입출력의 예

N result
5 [[1,2,3,4],[1,4,5],[2,3,5]]
2 []
7 [[1,2,3,4],[1,2,7],[1,3,6],[1,4,5],[2,3,5],[3,7],[4,6]]

❗ 1번째

백트래킹을 이용하라는 간단한 몸풀기 문제이다 크게 로직은 어렵지 않으니 잘 사용해보자

✅ 실행 코드

function solution(N) {
  const results = [];

  function back(sum, selectedNums, start) {
    if (sum === 10) {
      results.push(selectedNums);
      return;
    }

    for (let i = start; i <= N; i++) { 
      if (sum + i <= 10) {
        back(
          sum + i, selectedNums.concat(i), i + 1
        );
      }
    }
  }

  back(0, [], 1);
  return results;
}

📚 문제 느낀점

합이 10이 되는 조합만 골라야 하기때문에 불필요한 재귀 호출을 줄이고 중복없이 조합을 생성가능한 문제 백트래킹의 몸풀기 문제로 좋은거같다.

© 문제 출처

저자 출제